package class03



/*
	可以回顾一下动态规划的一些思路：
		1. 从左向右的尝试模型
		2. 范围上的尝试模型
		3. 位置对应的尝试模型
		4. 根据业务限制的尝试模型

	请注意区分子串与序列的不同，给定两个字符串str1，和str2
	求两个字符串的最长公共子序列

	两个字符串长度都为1时，相等为1，不相等为0
	遍历第一行与第一列，就是当s1与s2在等于一个字符的情况下，
	如果出现过1，后续都是1

	之后的每个格子都分可能性
	1. 最长公共子序列 最后一个字符为s1为结尾
	2. 最长公共子序列 最后一个字符为s2为结尾
	3. 最长公共子序列 最后一个字符为s2与s1为结尾
	4. 最长公共子序列 最后一个字符既不以s1也不以s2的最后一个字符为结尾
*/
func lcs(s1, s2 string) int {
	return lcsProcess(s1, s2, len(s1)-1, len(s2)-1)
}

func lcsProcess(s1, s2 string, end1, end2 int) int {
	if end1 == 0 && end2 == 0 {
		if s1[end1] == s2[end2] {
			return 1
		}
		return 0
	}
	if end1 == 0 {
		if s1[end1] == s2[end2] {
			return 1
		} else {
			return lcsProcess(s1, s2, end1, end2-1)
		}
	}
	if end2 == 0 {
		if s1[end1] == s2[end2] {
			return 1
		} else {
			return lcsProcess(s1, s2, end1-1, end2)
		}
	}

	var p1, p2, p3, p4 int
	p1 = lcsProcess(s1, s2, end1, end2-1)
	p2 = lcsProcess(s1, s2, end1-1, end2)
	p3 = lcsProcess(s1, s2, end1-1, end2-1)
	if s1[end1] == s2[end2] {
		p4 = p3 + 1
	}
	return max(max(p1, p2), max(p3, p4))
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func lcs2(s1, s2 string) int {
	dp := make([][]int, len(s1))
	for i:=0; i<len(dp); i++ {
		dp[i] = make([]int, len(s2))
	}
	if s1[0] == s2[0] {
		dp[0][0] = 1
	}
	for i:=1; i<len(s2); i++ {
		if s1[0] == s2[i] {
			dp[0][i] = 1
		} else {
			if dp[0][i-1] == 1 {
				dp[0][i] = 1
			}
		}
	}
	for i:=1; i<len(s1); i++ {
		if s2[0] == s1[i] {
			dp[i][0] = 1
		} else {
			if dp[i-1][0] == 1 {
				dp[i][0] = 1
			}
		}
	}
	for end1:=1; end1<len(s1); end1++ {
		for end2:=1; end2<len(s2); end2++ {
			dp[end1][end2] = max(dp[end1][end2-1], dp[end1-1][end2])
			if s1[end1] == s2[end2] {
				dp[end1][end2] = max(dp[end1][end2], dp[end1-1][end2-1]+1)
			}
		}
	}

	return dp[len(s1)-1][len(s2)-1]
}